#include <stdlib.h>
#include "tree_1.h"

//树的初始化函数
void tree_init(tree *p_tree) {
	p_tree->p_node = NULL;	//把树设置成没有节点的空树
}

//树的清理函数
void tree_deinit(tree *p_tree) {
	//采用后序遍历方式删除所有动态分配节点
	if(!p_tree->p_node) {
	//如果最上面的方块里是空指针就表示树里没有节点，这种时候也就不需要清理
		return;
	}
	tree_deinit(&(p_tree/*指向最上面的方块*/->p_node/*指向最上面的圆圈*/->left/*代表左子树的方块*/));	//清理左子树
	tree_deinit(&(p_tree->p_node->right));	//清理右子树
	free(p_tree->p_node);	//删除并释放根节点
	p_tree->p_node = NULL;
}

//在有序二叉树里查找某个数字所在位置的函数
tree * tree_search(const tree *p_tree, int val) {
	if(!p_tree->p_node) {
		return (tree *)p_tree;	//因为形参有const关键字，返回值没有const关键字，编译会有警告，所以返回值需要强制转换去掉const关键字。
	}
	if(p_tree->p_node->val == val) {
	//根节点里的数字就是要查找的数字
		return (tree *)p_tree;
	}
	else if(p_tree->p_node->val > val) {
	//当根节点里的数字比要查找的数字大，就应该在左子树里继续递归查找
		return tree_search(&(p_tree->p_node->left), val);	//在左子树里继续查找
	}
	else {
		return tree_search(&(p_tree->p_node->right), val);	//在右子树里继续查找
	}
}

//在有序二叉树里插入数字的函数
int tree_insert(tree *p_tree, int val) {
	node *p_node = NULL;
	tree *p_tmp = tree_search(p_tree, val);	//在有序二叉树里查找要插入的数字位置
	if(p_tmp->p_node) {
	//找到的位置下面有圆圈表示数字已经存在
		return 0;
	}
	p_node = (node *)malloc(sizeof(node));	//动态分配节点用来记录要插入的数字
	if(!p_node) {
	//动态分配内存失败
		return 0;
	}
	p_node->val = val;	//把要插入的数字记录到动态分配节点里
	p_node->left.p_node = NULL;
	p_node->right.p_node = NULL;
	p_tmp->p_node = p_node;	//把动态分配节点挂在找到的方块下面
	return 1;
}

/* 输出操作函数，可以省略放在主函数里。
void print_cb(int val) {
	printf("%d ", val);
}
*/

//以中序遍历方式，用pfunc_t p_func函数指针类型，处理树里所有节点的函数。
void tree_miter(const tree *p_tree, pfunc_t p_func) {
	if(!p_tree->p_node) {
		return ;
	}
	tree_miter(&(p_tree->p_node->left), p_func);	//递归调用tree_miter函数处理左子树
	p_func(p_tree->p_node->val);	//使用函数指针形参代表的函数处理根节点
	tree_miter(&(p_tree->p_node->right), p_func);	//递归调用tree_miter函数处理右子树
}
